//#pragma once
//#include<iostream>
//void Print(int* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		std::cout << arr[i] << " ";
//	}
//	std::cout << std::endl;
//}
//void Swap(int& x, int& y)
//{
//	int tmp = x;
//	x = y;
//	y = tmp;
//}
//void AdjustDown(int* arr,int n,int parent)
//{
//	int child = parent * 2 + 1;
//	while (child<n)
//	{
//		if (child+1<n&&arr[child+1]>arr[child])
//		{
//			child++;
//		}
//		if (arr[child]>arr[parent])
//		{
//			Swap(arr[child],arr[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//void HeapSort(int* arr,int n)
//{
//	for (int i=(n-1-1)/2;i>=0;i--)
//	{
//		AdjustDown(arr,n,i);
//	}
//
//	int end = n - 1;
//	while (end>=0)
//	{
//		Swap(arr[end],arr[0]);
//
//		AdjustDown(arr,end,0);
//		end--;
//	}
//}
//int main()
//{
//	int arr[] = { 5,9,1,6,2,3,4,8,7,10,15,11,16,12,14,13 };
//	int size = sizeof(arr) / sizeof(int);
//	HeapSort(arr,size);
//	Print(arr, size);
//	return 0;
//}